Description

213. House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 3:

Input: nums = [1,2,3]
Output: 3

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Answer & Explaining

#include <stdio.h>

// 函數 robLinear：計算從 start 到 end 的範圍內房屋的最大搶劫金額（忽略cycle限制）
int robLinear(int* nums, int start, int end) {
    int prev2 = 0, prev1 = 0;  // prev2 和 prev1 分別儲存前兩個狀態的最大金額
    for (int i = start; i <= end; i++) {  // 從起始位置遍歷到結束位置
        int temp = prev1;  // 暫存 prev1 的值
        // 更新 prev1，選擇不搶當前房子（保持 prev1）或搶當前房子（prev2 + nums[i]）的較大值
        prev1 = prev1 > prev2 + nums[i] ? prev1 : prev2 + nums[i];
        prev2 = temp;  // 更新 prev2 為上一個狀態的 prev1
    }
    return prev1;  // 返回最大搶劫金額
}

// 計算cycle排列的房屋最大搶劫金額
int rob(int* nums, int numsSize) {
    if (numsSize == 1) return nums[0];  // 若只有一間房子，直接返回該房子的金額
    // 計算忽略最後一間房子和忽略第一間房子的情況，並返回兩者的最大值
    return robLinear(nums, 0, numsSize - 2) > robLinear(nums, 1, numsSize - 1) 
           ? robLinear(nums, 0, numsSize - 2) 
           : robLinear(nums, 1, numsSize - 1);
}

Testing

#include <stdio.h>

// 函數 robLinear：計算從 start 到 end 的範圍內房屋的最大搶劫金額（忽略cycle限制）
int robLinear(int* nums, int start, int end) {
    int prev2 = 0, prev1 = 0;  // prev2 和 prev1 分別儲存前兩個狀態的最大金額
    for (int i = start; i <= end; i++) {  // 從起始位置遍歷到結束位置
        int temp = prev1;  // 暫存 prev1 的值
        // 更新 prev1，選擇不搶當前房子（保持 prev1）或搶當前房子（prev2 + nums[i]）的較大值
        prev1 = prev1 > prev2 + nums[i] ? prev1 : prev2 + nums[i];
        prev2 = temp;  // 更新 prev2 為上一個狀態的 prev1
    }
    return prev1;  // 返回最大搶劫金額
}

// 計算cycle排列的房屋最大搶劫金額
int rob(int* nums, int numsSize) {
    if (numsSize == 1) return nums[0];  // 若只有一間房子，直接返回該房子的金額
    // 計算忽略最後一間房子和忽略第一間房子的情況，並返回兩者的最大值
    return robLinear(nums, 0, numsSize - 2) > robLinear(nums, 1, numsSize - 1) 
           ? robLinear(nums, 0, numsSize - 2) 
           : robLinear(nums, 1, numsSize - 1);
}

// 測試函數
void test(int* nums, int numsSize, int expected) {
    int result = rob(nums, numsSize);
    printf("測試資料: [");
    for (int i = 0; i < numsSize; i++) {
        printf("%d", nums[i]);
        if (i < numsSize - 1) printf(", ");
    }
    printf("], 預期結果: %d, 函數結果: %d\n", expected, result);
    if (result == expected) {
        printf("測試通過！\n\n");
    } else {
        printf("測試失敗！\n\n");
    }
}

int main() {
    int nums1[] = {2, 3, 2};
    test(nums1, 3, 3);  // 預期輸出: 3

    int nums2[] = {1, 2, 3, 1};
    test(nums2, 4, 4);  // 預期輸出: 4

    int nums3[] = {1, 2, 3};
    test(nums3, 3, 3);  // 預期輸出: 3

    int nums4[] = {200, 3, 140, 20, 10};
    test(nums4, 5, 340);  // 預期輸出: 340

    return 0;
}